﻿using System;
using System.Collections.Generic;

namespace Socium.Domain.Collections
{
	[Serializable]
	public sealed class Set<T>
	{
		#region Delegates

		public delegate void Traverser(T value);
		private delegate void NodeTraverser(Node node);

		#endregion

		Node _root;
		int _count;

		static bool Insert(ref Node target, Node node)
		{
			if (target != null)
				return target.Add(node);

			target = node;
			return true;
		}

		public int Count
		{
			get { return _count; }
		}

		public bool Add(T item)
		{
			var node = new Node(item);
			if (Insert(ref _root, node))
			{
				_count++;
				return true;
			}

			return false;
		}

		public void AddRange(IEnumerable<T> items) {
			items.Iterate(item => Add(item));
		}

		static void Traverse(Node node, NodeTraverser traverser)
		{
			if (node != null)
				node.Traverse(traverser);
		}

		public void Traverse(Traverser traverser)
		{
			Traverse(_root, node => traverser(node.Item));
		}

		void Traverse(NodeTraverser traverser)
		{
			Traverse(_root, traverser);
		}

		static bool Contains(Node node, Node pattern)
		{
			if (node == null)
				return false;

			return node.Contains(pattern);
		}

		public bool Contains(T item)
		{
			var pattern = new Node(item);
			return Contains(_root, pattern);
		}

		class ArrayTraverser<TItem>
		{
			private int _index;
			private readonly TItem[] _data;

			public ArrayTraverser(int count)
			{
				_data = new TItem[count];
			}

			public void Traverse(TItem item)
			{
				_data[_index] = item;
				_index++;
			}

			public TItem[] GetItems()
			{
				return _data;
			}
		}

		public void Balance()
		{
			var count = Count;
			if (count == 0)
				return;

			var traverser = new ArrayTraverser<Node>(count);
			Traverse(traverser.Traverse);

			var nodes = traverser.GetItems();
			var range = new IndexRange(count);
			_root = Node.FromArray(nodes, range);
		}

		public T[] ToArray()
		{
			var traverser = new ArrayTraverser<T>(Count);
			Traverse(traverser.Traverse);

			return traverser.GetItems();
		}

		public void Clear()
		{
			_root = null;
			_count = 0;
		}

		#region Nested type: IndexRange

		struct IndexRange
		{
			readonly int _finish;
			readonly int _start;

			/*public */
			IndexRange(int start, int finish)
			{
				_start = start;
				_finish = finish;
			}

			public IndexRange(int count)
				: this(0, count - 1)
			{
			}

			public bool IsValid
			{
				get { return _start >= 0 && _start <= _finish; }
			}

			public int GetCenter()
			{
				return (_start + _finish) / 2;
			}

			public IndexRange GetLeftPart(int center)
			{
				return new IndexRange(_start, center - 1);
			}

			public IndexRange GetRightPart(int center)
			{
				return new IndexRange(center + 1, _finish);
			}

			public override string ToString()
			{
				return string.Format("Start: {0}, Finish: {1}", _start, _finish);
			}
		}

		#endregion

		#region Nested type: Node

		[Serializable]
		class Node : IEquatable<Node>, IComparable<Node>
		{
			readonly int _hash;
			public readonly T Item;

			Node _left;
			Node _right;

			public Node(T value)
			{
				Item = value;
				_hash = value.GetHashCode();
			}

			#region IComparable<Set<T>.Node> Members

			public int CompareTo(Node other)
			{
				if (Equals(other))
					return 0;

				if (_hash < other._hash)
					return -1;

				return 1;
			}

			#endregion

			#region IEquatable<Set<T>.Node> Members

			public bool Equals(Node obj)
			{
				if (ReferenceEquals(null, obj))
					return false;
				if (ReferenceEquals(this, obj))
					return true;
				//return obj._hash == _hash && Equals(obj._item, _item);
				return Item.Equals(obj.Item);
			}

			#endregion

			public void Traverse(NodeTraverser traverser)
			{
				Set<T>.Traverse(_left, traverser);
				traverser(this);
				Set<T>.Traverse(_right, traverser);
			}

			public override bool Equals(object obj)
			{
				if (ReferenceEquals(null, obj))
					return false;
				if (ReferenceEquals(this, obj))
					return true;
				if (obj.GetType() != typeof(Node))
					return false;
				return Equals((Node)obj);
			}

			public override int GetHashCode()
			{
				unchecked
				{
					return (_hash * 397) ^ Item.GetHashCode();
				}
			}

			public static bool operator ==(Node left, Node right)
			{
				return Equals(left, right);
			}

			public static bool operator !=(Node left, Node right)
			{
				return !Equals(left, right);
			}

			public static bool operator <(Node left, Node right)
			{
				return left.CompareTo(right) < 0;
			}

			public static bool operator >(Node left, Node right)
			{
				return left.CompareTo(right) > 0;
			}

			public bool Add(Node node)
			{
				if (node == this)
					return false;

				if (node < this)
					return Insert(ref _left, node);

				return Insert(ref _right, node);
			}

			public bool Contains(Node node)
			{
				if (node == this)
					return true;

				if (node < this)
					return Set<T>.Contains(_left, node);

				return Set<T>.Contains(_right, node);
			}

			public override string ToString()
			{
				return string.Format("Hash: {0}, Item: {1}", _hash, Item);
			}

			public static Node FromArray(Node[] array, IndexRange range)
			{
				if (!range.IsValid)
					return null;

				var center = range.GetCenter();
				var node = array[center];

				node._left = FromArray(array, range.GetLeftPart(center));
				node._right = FromArray(array, range.GetRightPart(center));

				return node;
			}
		}

		#endregion
	}
}